#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *
 *
 *1143.最⻓公共⼦序列
给定两个字符串 text1 和 text2，返回这两个字符串的最⻓公共⼦序列的⻓度。
⼀个字符串的 ⼦序列 是指这样⼀个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除
某些字符（也可以不删除任何字符）后组成的新字符串。
return result;
}
};
例如，"ace" 是 "abcde" 的⼦序列，但 "aec" 不是 "abcde" 的⼦序列。两个字符串的「公共⼦序列」是
这两个字符串所共同拥有的⼦序列。
若这两个字符串没有公共⼦序列，则返回 0。
示例 1:
输⼊：text1 = "abcde", text2 = "ace"
输出：3
解释：最⻓公共⼦序列是 "ace"，它的⻓度为 3。
示例 2:
输⼊：text1 = "abc", text2 = "abc"
输出：3
解释：最⻓公共⼦序列是 "abc"，它的⻓度为 3。
示例 3:
输⼊：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共⼦序列，返回 0。
提示:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
输⼊的字符串只含有⼩写英⽂字符。
 *
 *
 * */


int longestCommonSubsequence(string text1, string text2) {


    vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));

    int maxV=0;

    for (int i = 1; i <=text1.size() ; ++i) {

        for (int j = 1; j <=text2.size() ; ++j) {

            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }

            maxV=max(maxV,dp[i][j]);

        }


    }


    return maxV;


}